{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "233168\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "on =time.time()\n",
    "\n",
    "j = 0\n",
    "for i in range(3,1000):\n",
    "    if i%3==0 or i%5==0:\n",
    "        j = j+i\n",
    "print(j)\n",
    "\n",
    "print(time.time()-on)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4613732\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "#斐波那契数列中的每一项被定义为前两项之和。从1和2开始，斐波那契数列的前十项为：\n",
    "\n",
    "#1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n",
    "\n",
    "#考虑斐波那契数列中数值不超过4百万的项，找出这些项中值为偶数的项之和。\n",
    "import time\n",
    "on = time.time()\n",
    "\n",
    "data1=1\n",
    "data2=2\n",
    "data3=data1+data2\n",
    "res_sum = data2\n",
    "while data3<=4000000:\n",
    "    if data3%2==0:\n",
    "        res_sum = res_sum + data3\n",
    "    data1 = data2\n",
    "    data2 = data3\n",
    "    data3 = data1 + data2\n",
    "print(res_sum)\n",
    "\n",
    "print(time.time()-on)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[71, 839, 1471, 6857]\n",
      "0.0020003318786621094\n"
     ]
    }
   ],
   "source": [
    "#13195的质数因子有5,7,13和29.\n",
    "\n",
    "#600851475143的最大质数因子是多少？\n",
    "import time\n",
    "on = time.time()\n",
    "\n",
    "def getList(n):\n",
    "    result = []\n",
    "    count = 3\n",
    "    max = n\n",
    "    while max%2 == 0:\n",
    "        max /= 2\n",
    "        result.append(2)\n",
    "    \n",
    "    while count <= max:\n",
    "        while max%count == 0:\n",
    "            result.append(count)\n",
    "            max /= count\n",
    "        count += 2\n",
    "    return result\n",
    "print(getList(600851475143))\n",
    "\n",
    "print(time.time()-on)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "906609 = 993 * 913\n",
      "Wall time: 119 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "##\n",
    "#一个回文数指的是从左向右和从右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是9009 = 91 * 99.\n",
    "\n",
    "#找出最大的有由个三位数乘积构成的回文数。\n",
    "#\n",
    "import time\n",
    "on = time.time()\n",
    "res_i_j=(100,100)\n",
    "max_huiwen = 0\n",
    "for i in range(999,99,-1):\n",
    "    for j in range(999,99,-1):\n",
    "        res = i*j\n",
    "        if res<max_huiwen:\n",
    "            continue\n",
    "        if str(res)==str(res)[::-1]:\n",
    "            if res>max_huiwen:\n",
    "                max_huiwen = res\n",
    "                res_i_j = i,j\n",
    "\n",
    "print(\"%d = %d * %d\" % (max_huiwen,res_i_j[0],res_i_j[1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "232792560\n",
      "0.0010008811950683594\n"
     ]
    }
   ],
   "source": [
    "#2520是最小的能被1-10中每个数字整除的正整数。\n",
    "#最小的能被1-20中每个数整除的正整数是多少？print(time.time()-on)\n",
    "#如果要满足被所有20以内的整数整除这个数必须满足含有各个合数最多个数的质因子。\n",
    "#首先找出所有质因子\n",
    "import time\n",
    "on = time.time()\n",
    "import math\n",
    "import numpy as np\n",
    "\n",
    "def is_prime(num):\n",
    "    if num<2:\n",
    "        return False\n",
    "    if num==2:\n",
    "        return True\n",
    "    for i in range(2,math.floor(math.sqrt(num))+1):\n",
    "        if num%i==0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "primes=[]\n",
    "dic = {}#用来存放每个质因子的最大次数\n",
    "for i in range(2,21):\n",
    "    if is_prime(i):\n",
    "        primes.append(i)\n",
    "        dic[i]=1\n",
    "    else:#是合数\n",
    "        ori=i\n",
    "        a = np.array(primes)\n",
    "        for j in a[a<=math.sqrt(i)]:\n",
    "            nums=0\n",
    "            while ori%j==0:\n",
    "                nums += 1\n",
    "                ori = ori//j\n",
    "            if dic[j]<nums:\n",
    "                dic[j]=nums\n",
    "res = 1\n",
    "for k,v in dic.items():\n",
    "    res = (k**v) * res\n",
    "print(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25164150"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#前十个自然数的平方和是：\n",
    "#12 + 22 + ... + 102 = 385\n",
    "\n",
    "#前十个自然数的和的平方是：\n",
    "#(1 + 2 + ... + 10)2 = 552 = 3025\n",
    "\n",
    "#所以平方和与和的平方的差是3025 − 385 = 2640.\n",
    "\n",
    "#找出前一百个自然数的平方和与和平方的差。\n",
    "\n",
    "import numpy as np\n",
    "a = np.array(range(1,101))\n",
    "(sum(a))**2-sum(a**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "104743\n",
      "0.8475987911224365\n"
     ]
    }
   ],
   "source": [
    "#前六个质数是2,3,5,7,11和13，其中第6个是13.\n",
    "\n",
    "#第10001个质数是多少？\n",
    "\n",
    "import time\n",
    "on=time.time()\n",
    "\n",
    "from itertools import takewhile,count\n",
    "def prime(n):\n",
    "    nums = filter(lambda x:x % 10 in (1,3,7,9) or x in (2,5), count(2))\n",
    "    nums = (num for num in nums if [i for i in range(2, int(num ** 0.5) + 1) if num % i == 0] == [])\n",
    "    return next((num for idx,num in enumerate(nums, start=1) if idx == n))\n",
    "print(prime(10001))\n",
    "\n",
    "print(time.time()-on)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13位连乘，积的最大值：23514624000\n",
      "这13位数是：5576689664895\n"
     ]
    }
   ],
   "source": [
    "#找出以下这个1000位的整数中连续13个数字的最大乘积。\n",
    "from functools import reduce\n",
    "\n",
    "def mul_13(s):\n",
    "    return reduce(lambda x,y: x * y,map(int,s))\n",
    "\n",
    "goal_string = '''73167176531330624919225119674426574742355349194934\n",
    " 96983520312774506326239578318016984801869478851843\n",
    " 85861560789112949495459501737958331952853208805511\n",
    " 12540698747158523863050715693290963295227443043557\n",
    " 66896648950445244523161731856403098711121722383113\n",
    " 62229893423380308135336276614282806444486645238749\n",
    " 30358907296290491560440772390713810515859307960866\n",
    " 70172427121883998797908792274921901699720888093776\n",
    " 65727333001053367881220235421809751254540594752243\n",
    " 52584907711670556013604839586446706324415722155397\n",
    " 53697817977846174064955149290862569321978468622482\n",
    " 83972241375657056057490261407972968652414535100474\n",
    " 82166370484403199890008895243450658541227588666881\n",
    " 16427171479924442928230863465674813919123162824586\n",
    " 17866458359124566529476545682848912883142607690042\n",
    " 24219022671055626321111109370544217506941658960408\n",
    " 07198403850962455444362981230987879927244284909188\n",
    " 84580156166097919133875499200524063689912560717606\n",
    " 05886116467109405077541002256983155200055935729725\n",
    " 71636269561882670428252483600823257530420752963450'''\n",
    "goal_string = goal_string.replace(\"\\n \",\"\")\n",
    "goal_lists=goal_string.split(\"0\")\n",
    "\n",
    "the_max = 0\n",
    "for li in goal_lists:\n",
    "    length = len(li)\n",
    "    if length<13:\n",
    "        continue\n",
    "    else:\n",
    "        for i in range(length-12):\n",
    "            s = li[i:i+13]\n",
    "            res = mul_13(s)\n",
    "            if res > the_max:\n",
    "                the_max = res\n",
    "                max_string = s\n",
    "\n",
    "print(\"13位连乘，积的最大值：\"+str(the_max))\n",
    "print(\"这13位数是：\"+ max_string)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "31875000\n",
      "0.4844057354965443\n"
     ]
    }
   ],
   "source": [
    "#找出唯一的满足a + b + c = 1000的毕达哥拉斯三元组{a, b, c}。 \n",
    "import time\n",
    "on = time.clock()\n",
    "for c in range(250,1001):\n",
    "    for a in range(1,max(500,int(c*1.414/2))):\n",
    "        if a**2+(1000-c-a)**2==c**2:\n",
    "            res = (a,1000-a-c,c)\n",
    "print(res[0]*res[1]*res[2])\n",
    "print(time.clock()-on)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
